﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0198_UniqueLetterString : IAlgorithm
    {
        // 828. 统计子串中的唯一字符

        /*
        我们定义了一个函数 countUniqueChars(s) 来统计字符串 s 中的唯一字符，并返回唯一字符的个数。
        例如：s = "LEETCODE" ，则其中 "L", "T","C","O","D" 都是唯一字符，因为它们只出现一次，所以 countUniqueChars(s) = 5 。
        本题将会给你一个字符串 s ，我们需要返回 countUniqueChars(t) 的总和，其中 t 是 s 的子字符串。输入用例保证返回值为 32 位整数。
        注意，某些子字符串可能是重复的，但你统计时也必须算上这些重复的子字符串（也就是说，你必须统计 s 的所有子字符串中的唯一字符）。

        提示：
            1 <= s.length <= 10^5
            s 只包含大写英文字符 
        */

        public void Test()
        {

        }

        // 算法
        public int UniqueLetterString(string s)
        {
            Dictionary<char, IList<int>> index = new Dictionary<char, IList<int>>();
            for (int i = 0; i < s.Length; i++)
            {
                if (!index.ContainsKey(s[i]))
                {
                    index.Add(s[i], new List<int>());
                    index[s[i]].Add(-1);
                }
                index[s[i]].Add(i);
            }
            int res = 0;
            foreach (KeyValuePair<char, IList<int>> pair in index)
            {
                IList<int> arr = pair.Value;
                arr.Add(s.Length);
                for (int i = 1; i < arr.Count - 1; i++)
                {
                    res += (arr[i] - arr[i - 1]) * (arr[i + 1] - arr[i]);
                }
            }
            return res;
        }
    }
}
